﻿#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<queue>
#include<cstring>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>

using namespace std;

//-------------------------------------------------------递归、搜索与回溯算法-------------------------------------------------------------

//1. 汉诺塔

//递归函数设计：void hanotaa(vector<int>& A, vector<int>& B, vector<int>& C, int n)
//1. 返回值：无；
//2. 参数：三个柱子上的盘子，当前需要处理的盘⼦个数（当前问题规模）。
//3. 函数作⽤：将 A 中的上⾯ n 个盘⼦挪到 C 中。
//递归函数流程：
//1. 当前问题规模为 n = 1 时，直接将 A 中的最上⾯盘⼦挪到 C 中并返回；
//2. 递归将 A 中最上⾯的 n - 1 个盘⼦挪到 B 中；
//3. 将 A 中最上⾯的⼀个盘⼦挪到 C 中；
//4. 将 B 中上⾯ n - 1 个盘⼦挪到 C 中。

//画图

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C)
    {
        dfs(A, B, C, A.size());
    }
    void dfs(vector<int>& A, vector<int>& B, vector<int>& C, int n)
    {
        if (n == 1)
        {
            C.push_back(A.back()); A.pop_back();
            return;
        }
        dfs(A, C, B, n - 1);
        C.push_back(A.back()); A.pop_back();
        dfs(B, A, C, n - 1);

    }
};


//2. 合并两个有序链表

//1. 递归函数的含义：交给你两个链表的头结点，你帮我把它们合并起来，并且返回合并后的头结点；
//2. 函数体：选择两个头结点中较⼩的结点作为最终合并后的头结点，然后将剩下的链表交给递归函数去处理；
//3. 递归出⼝：当某⼀个链表为空的时候，返回另外⼀个链表。
//注意注意注意：链表的题⼀定要画图，搞清楚指针的操作！

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
    {
        if (l1 == nullptr)return l2;
        if (l2 == nullptr)return l1;

        if (l1->val <= l2->val)
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = mergeTwoLists(l2->next, l1);
            return l2;
        }
    }
};


//3. 反转链表

//算法思路：
//1. 递归函数的含义：交给你⼀个链表的头指针，你帮我逆序之后，返回逆序后的头结点；
//2. 函数体：先把当前结点之后的链表逆序，逆序完之后，把当前结点添加到逆序后的链表后⾯即可；
//3. 递归出⼝：当前结点为空或者当前只有⼀个结点的时候，不⽤逆序，直接返回。
//注意注意注意：链表的题⼀定要画图，搞清楚指针的操作！

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode* reverseList(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr)return head;

        ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;


        return newhead;
    }
};


//4. 两两交换链表中的节点

//1. 递归函数的含义：交给你⼀个链表，将这个链表两两交换⼀下，然后返回交换后的头结点；
//2. 函数体：先去处理⼀下第⼆个结点往后的链表，然后再把当前的两个结点交换⼀下，连接上后⾯处理后的链表；
//3. 递归出口：当前结点为空或者当前只有⼀个结点的时候，不⽤交换，直接返回。

//注意注意注意：链表的题⼀定要画图，搞清楚指针的操作！

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr)return head;

        ListNode* tmp = swapPairs(head->next->next);

        head->next->next = head;
        ListNode* ret = head->next;
        head->next = tmp;

        return ret;
    }
};


//5. Pow（x, n） - 快速幂

//算法思路：
//1. 递归函数的含义：求出 x 的 n 次⽅是多少，然后返回；
//2. 函数体：先求出 x 的 n / 2 次⽅是多少，然后根据 n 的奇偶，得出 x 的 n 次⽅是多少；
//3. 递归出口：当 n 为 0 的时候，返回 1 即可。

class Solution {
public:
    double myPow(double x, int n)
    {
        return n < 0 ? 1.0 / pow(x, -(long long)n) : pow(x, (long long)n);
    }

    double pow(double x, long long n)
    {
        if (n == 0)return 1;

        double tmp = myPow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
};


//-------------------------------------------------------------⼆叉树中的深搜------------------------------------------------------------


//6. 计算布尔⼆叉树的值

//算法思路：
//本题可以被解释为：
//1. 对于规模为 n 的问题，需要求得当前节点值。
//2. 节点值不为 0 或 1 时，规模为 n 的问题可以被拆分为规模为 n - 1 的⼦问题：
//a.所有⼦节点的值；
//b.通过⼦节点的值运算出当前节点值。
//3. 当问题的规模变为 n = 1 时，即叶⼦节点的值为 0 或 1，我们可以直接获取当前节点值为 0 或 1。
// 
//算法流程：
//递归函数设计：bool evaluateTree(TreeNode * root)
//1. 返回值：当前节点值；
//2. 参数：当前节点指针。
//3. 函数作⽤：求得当前节点通过逻辑运算符得出的值。
// 
//递归函数流程：
//1. 当前问题规模为 n = 1 时，即叶⼦节点，直接返回当前节点值；
//2. 递归求得左右⼦节点的值；
//3. 通过判断当前节点的逻辑运算符，计算左右⼦节点值运算得出的结果；

 // Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };

class Solution
{
public:
    bool evaluateTree(TreeNode* root)
    {
        if (root->left == nullptr)return root->val == 0 ? false : true;
        bool flag1 = evaluateTree(root->left);
        bool flag2 = evaluateTree(root->right);
        if (root->val == 2)return flag1 | flag2;
        else return flag1 & flag2;
    }
};


//7. 求根节点到叶节点数字之和

//算法思路：
//在前序遍历的过程中，我们可以往左右⼦树传递信息，并且在回溯时得到左右⼦树的返回值。
//递归函数可以帮我们完成两件事：
//1. 将⽗节点的数字与当前节点的信息整合到⼀起，计算出当前节点的数字，然后传递到下⼀层进⾏递归；
//2. 当遇到叶⼦节点的时候，就不再向下传递信息，⽽是将整合的结果向上⼀直回溯到根节点。
//在递归结束时，根节点需要返回的值也就被更新为了整棵树的数字和。
//
//算法流程：
//递归函数设计：int dfs(TreeNode * root, int num)
//1. 返回值：当前⼦树计算的结果（数字和）；
//2. 参数 num：递归过程中往下传递的信息（⽗节点的数字）；
//3. 函数作⽤：整合⽗节点的信息与当前节点的信息计算当前节点数字，并向下传递，在回溯时返回当前⼦树（当前节点作为⼦树根节点）数字和。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root)
    {
        return dfs(root, 0);
    }

    int dfs(TreeNode* root, int sum)
    {
        sum = sum * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr)return sum;
        int ret = 0;
        if (root->left)ret += dfs(root->left, sum);
        if (root->right)ret += dfs(root->right, sum);
        return ret;
    }
};


//8. ⼆叉树剪枝

//在后序遍历中，我们先处理左⼦树，然后处理右⼦树，最后再处理当前节点。
//在处理当前节点时，我们可以判断其是否为叶⼦节点且其值是否为 0，
//如果满⾜条件，我们可以删除当前节点。

//后序遍历的主要流程：
//
//1. 递归出⼝：当传⼊节点为空时，不做任何处理；
//2. 递归处理左⼦树；
//3. 递归处理右⼦树；
//4. 处理当前节点：判断该节点是否为叶⼦节点（即左右⼦节点均被删除，当前节点成为叶⼦节点），并且节点的值为 0：
//    a.如果是，就删除掉；
//    b.如果不是，就不做任何处理。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* pruneTree(TreeNode* root)
    {
        if (root == nullptr)return nullptr;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        if (root->left == nullptr && root->right == nullptr && root->val == 0)
        {
            root = nullptr;//不需要真正的删除 置为0即可
        }
        return root;
    }
};


//9. 验证⼆叉搜索树

//1. 初始化⼀个全局的变量 prev，⽤来记录中序遍历过程中的前驱结点的 val；
//2. 中序遍历的递归函数中：
//a.设置递归出⼝：root == nullptr 的时候，返回 true；
//b.先递归判断左⼦树是否是⼆叉搜索树，⽤ retleft 标记；
//c.然后判断当前结点是否满⾜⼆叉搜索树的性质，⽤ retcur 标记：
//▪ 如果当前结点的 val ⼤于 prev，说明满⾜条件，retcur 改为 true；
//▪ 如果当前结点的 val ⼩于等于 prev，说明不满⾜条件，retcur 改为 false；
//d.最后递归判断右⼦树是否是⼆叉搜索树，⽤ retright 标记；
//3. 只有当 retleft、 retcur 和 retright 都是 true 的时候，才返回 true。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
    long MIN = LONG_MIN;
public:
    bool isValidBST(TreeNode* root)
    {
        if (root == nullptr)return true;
        bool f1 = isValidBST(root->left);
        if (f1 == false)return false;

        bool cur = false;
        if (root->val > MIN)
        {
            cur = true;
        }
        MIN = root->val;
        bool f2 = isValidBST(root->right);

        return f1 & f2 & cur;
    }
};


//10. ⼆叉搜索树中第 k ⼩的元素

//因此，我们可以创建⼀个全局的计数器 count，将其初始化为 k，每遍历⼀个节点就将 count--。
//直到某次递归的时候，count 的值等于 1，说明此时的结点就是我们要找的结果。

//算法流程：
//1. 定义⼀个全局的变量 count，在主函数中初始化为 k 的值（不⽤全局也可以，当成参数传⼊递归过
//程中）；
//递归函数的设计：int dfs(TreeNode * root)：
//• 返回值为第 k 个结点；

//递归函数流程（中序遍历）：
//1. 递归出⼝：空节点直接返回 - 1，说明没有找到；
//2. 去左⼦树上查找结果，记为 retleft：
//a.如果 retleft == -1，说明没找到，继续执⾏下⾯逻辑；
//b.如果 retleft != -1，说明找到了，直接返回结果，⽆需执⾏下⾯代码（剪枝）；
//3. 如果左⼦树没找到，判断当前结点是否符合：
//a.如果符合，直接返回结果
//4. 如果当前结点不符合，去右⼦树上寻找结果。


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
    int count = 0, ret = 0;
public:
    int kthSmallest(TreeNode* root, int k)
    {
        count = k;
        dfs(root);
        return ret;
    }
    void dfs(TreeNode* root)
    {
        if (count == 0 || root == nullptr)return;
        dfs(root->left);
        count--;
        if (count == 0)ret = root->val;
        dfs(root->right);
    }

};



//11. ⼆叉树的所有路径

//1. 定义⼀个结果数组和⼀个路径数组。
//2. 从根节点开始递归，递归函数的参数为当前节点、结果数组和路径数组。
//a.如果当前节点为空，返回。
//b.将当前节点的值加入到路径数组中。
//c.如果当前节点为叶⼦节点，将路径数组中的所有元素拼接成字符串，并将该字符串存储到结果数组中。
//d.递归遍历当前节点的左⼦树。
//e.递归遍历当前节点的右⼦树。
//f.回溯，将路径数组中的最后⼀个元素移除，以返回到上⼀个节点。
//3. 返回结果数组。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
    vector<string> ret;
public:
    vector<string> binaryTreePaths(TreeNode* root)
    {
        string path;
        dfs(root, path);
        return ret;
    }

    void dfs(TreeNode* root, string path)
    {
        path += to_string(root->val);
        if (root->left == nullptr && root->right == nullptr)
        {
            ret.push_back(path);
            return;
        }
        path += "->";
        if (root->left)dfs(root->left, path);
        if (root->right)dfs(root->right, path);
        //剪枝、回溯
    }
};


//----------------------------------------------穷举vs暴搜vs深搜vs回溯vs剪枝----------------------------------------------------------------


//12. 全排列

//1. ⾸先定义⼀个⼆维数组 res ⽤来存放所有可能的排列，⼀个⼀维数组 ans ⽤来存放每个状态的排列，⼀个⼀维数组 visited 标记元素，然后从第⼀个位置开始进⾏递归；
//2. 在每个递归的状态中，我们维护⼀个步数 step，表⽰当前已经处理了⼏个数字；
//3. 递归结束条件：当 step 等于 nums 数组的⻓度时，说明我们已经处理完了所有数字，将当前数组存⼊结果中；
//4. 在每个递归状态中，枚举所有下标 i，若这个下标未被标记，则使⽤ nums 数组中当前下标的元
//素：
//a.将 visited[i] 标记为 1；
//b.ans 数组中第 step 个元素被 nums[i] 覆盖；
//c.对第 step + 1 个位置进⾏递归；
//d.将 visited[i] 重新赋值为 0，表⽰回溯；
//5. 最后，返回 res。
//• 特别地，我们可以不使⽤标记数组，直接遍历 step 之后的元素（未被使⽤），然后将其与需要递归的位置进⾏交换即可。

class Solution
{
    vector<vector<int>> ret;
    vector<int> path;
    bool check[7];
public:
    vector<vector<int>> permute(vector<int>& nums)
    {
        dfs(nums);
        return ret;
    }

    void dfs(vector<int>& nums)
    {
        if (nums.size() == path.size())
        {
            ret.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++)
        {
            if (check[i] == false)
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums);
                path.pop_back();
                check[i] = false;
            }
        }
    }
};


//13. ⼦集

//递归函数设计：void dfs(vector<vector<int>>& res, vector<int>& ans, vector<int>& nums, int step)
//    参数：step（当前需要处理的元素下标）；
//    返回值：⽆；
//    函数作⽤：查找集合的所有⼦集并存储在答案列表中。

//    递归流程如下：
//    1. 递归结束条件：如果当前需要处理的元素下标越界，则记录当前状态并直接返回；
//    2. 在递归过程中，对于每个元素，我们有两种选择：
//    ◦ 不选择当前元素，直接递归到下⼀个元素；
//    ◦ 选择当前元素，将其添加到数组末尾后递归到下⼀个元素，然后在递归结束时撤回添加操作；
//    3. 所有符合条件的状态都被记录下来，返回即可。

class Solution
{
    vector<vector<int>> ret;
    vector<int> path;
public:
    vector<vector<int>> subsets(vector<int>& nums)
    {
        dfs(nums, 0);
        return ret;
    }
    void dfs(vector<int>& nums, int pos)
    {
        ret.push_back(path);
        for (int i = pos; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }
};


//--------------------------------------------------------综合练习-----------------------------------------------------------------------


//14. 找出所有⼦集的异或总和再求和

//本题我们需要求出所有⼦集，将它们的异或和相加。
//因为异或操作满⾜交换律，所以我们可以定义⼀个变量，直接记录当前状态的异或和。
//使⽤递归保存当前集合的状态（异或和），选择将当前元素添加⾄当前状态与否，并依次递归数组中下⼀个元素。
//当递归到空元素时，表⽰所有元素都被考虑到，记录当前状态（将当前状态的异或和添加⾄答案中）。

class Solution
{
    int sum = 0;
    int path = 0;
public:
    int subsetXORSum(vector<int>& nums)
    {
        dfs(nums, 0);
        return sum;
    }
    void dfs(vector<int>& nums, int pos)
    {
        sum += path;
        for (int i = pos; i < nums.size(); i++)
        {
            path ^= nums[i];
            dfs(nums, i + 1);
            path ^= nums[i];
        }
    }
};

//15. 全排列 Ⅱ

//1. 定义⼀个⼆维数组 ans ⽤来存放所有可能的排列，⼀个⼀维数组 perm ⽤来存放每个状态的排列，
//⼀个⼀维数组 visited 标记元素，然后从第⼀个位置开始进⾏递归；
//2. 在每个递归的状态中，我们维护⼀个步数 idx，表⽰当前已经处理了⼏个数字；
//3. 递归结束条件：当 idx 等于 nums 数组的⻓度时，说明我们已经处理完了所有数字，将当前数组存⼊结果中；
//4. 在每个递归状态中，枚举所有下标 i，若这个下标未被标记，并且在它之前的相同元素被标记过，
//则使⽤ nums 数组中当前下标的元素：
//a.将 visited[i] 标记为 1；
//b.将 nums[i] 添加⾄ perm 数组末尾；
//c.对第 step + 1 个位置进⾏递归；
//d.将 visited[i] 重新赋值为 0，并删除 perm 末尾元素表⽰回溯；
//5. 最后，返回 ans。

class Solution
{
    vector<vector<int>> ret;
    vector<int> path;
    bool check[10];
public:
    vector<vector<int>> permuteUnique(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());//前提是要排序 那么相同的树就会在一块儿！
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos)
    {
        if (pos == nums.size())
        {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            if (check[i] == false && (i == 0 || nums[i - 1] != nums[i] || check[i - 1] != false))
                //第一个元素可以大胆使用！
                //前一个不等于后一个也可以使用
                //前=后但是前一个使用过 那么后一个也可以使用！
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums, pos + 1);
                path.pop_back();
                check[i] = false;
            }
        }
    }
};



//16. 电话号码的字⺟组合

//1. 递归结束条件：当 index 等于 digits 的⻓度时，将 ans 加⼊到 res 中并返回；
//2. 取出当前处理的数字 digit，根据 phoneMap 取出对应的字⺟列表 letters；
//3. 遍历字⺟列表 letters，将当前字⺟加⼊到组合字符串 ans 的末尾，然后递归处理下⼀个数字（传⼊ index + 1，表⽰处理下⼀个数字）；
//4. 递归处理结束后，将加⼊的字⺟从 ans 的末尾删除，表⽰回溯。
//5. 最终返回 res 即可。

class Solution
{
    vector<string> ret;
    string path;
    string hash[12] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
public:
    vector<string> letterCombinations(string digits)
    {
        if (digits.size() == 0)return ret;
        dfs(digits, 0);
        return ret;
    }

    void dfs(string digits, int pos)
    {
        if (pos == digits.size())
        {
            ret.push_back(path);
            return;
        }

        for (auto ch : hash[digits[pos] - '0'])
        {
            path += ch;
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
};


//17. 括号⽣成

//1. 放⼊左括号时需判断此时左括号数量是否⼩于字符串总⻓度的⼀半
//（若左括号的数量⼤于等于字符串⻓度的⼀半时继续放置左括号，则左括号的总数量⼀定⼤于右括号的总数量）；
//2. 放⼊右括号时需判断此时右括号数量是否⼩于左括号数量。

//递归函数参数设置为当前状态的字符串⻓度以及当前状态的左括号数量，递归流程如下：
//1. 递归结束条件：当前状态字符串⻓度与 2 * n 相等，记录当前状态并返回；
//2. 若此时左括号数量⼩于字符串总⻓度的⼀半，则在当前状态的字符串末尾添加左括号并继续递归，递归结束撤销添加操作；
//3. 若此时右括号数量⼩于左括号数量（右括号数量可以由当前状态的字符串⻓度减去左括号数量求得）
// 则在当前状态的字符串末尾添加右括号并递归，递归结束撤销添加操作；


class Solution
{
    vector<string> ret;
    string path;
    int n;
    int l = 0, r = 0;
public:
    vector<string> generateParenthesis(int _n)
    {
        n = _n;
        dfs();
        return ret;
    }

    void dfs()
    {

        if (r == n)
        {
            ret.push_back(path);
            return;
        }
        if (l < n)
        {
            path.push_back('(');
            l++;
            dfs();
            path.pop_back();
            l--;
        }
        if (l > r)
        {
            path.push_back(')');
            r++;
            dfs();
            path.pop_back();
            r--;
        }
    }
};


//18. 组合

//1. 定义⼀个⼆维数组和⼀维数组。⼆维数组⽤来记录所有组合，⼀维数组⽤来记录当前状态下的组合。
//2. 遍历 1 到 n - k + 1，以当前数作为组合的⾸位元素进⾏递归（从 n - k + 1 到 n 作为⾸位元素时，组合中⼀定不会存在 k 个元素）。
//3. 递归函数的参数为两个数组、当前步骤以及 n 和 k。递归流程如下：
//a.结束条件：当前组合中已经有 k 个元素，将当前组合存进⼆维数组并返回。
//▪ 剪枝：如果当前位置之后的所有元素放⼊组合也不能满⾜组合中存在 k 个元素，直接返回。
//b.从当前位置的下⼀个元素开始遍历到 n，将元素赋值到当前位置，递归下⼀个位置

class Solution
{
    vector<vector<int>> ret;
    vector<int> path;
    int n, k;
public:
    vector<vector<int>> combine(int nn, int kk)
    {
        n = nn; k = kk;
        dfs(1);
        return ret;
    }

    void dfs(int start)
    {
        if (path.size() == k)
        {
            ret.push_back(path);
            return;
        }

        for (int i = start; i <= n; i++)
        {
            path.push_back(i);
            dfs(i + 1);
            path.pop_back();
        }
    }
};


//19. ⽬标和

//对于每个数，可以选择加上或减去它，依次枚举每⼀个数字，
//在每个数都被选择时检查得到的和是否等于⽬标值。
//如果等于，则记录结果。
//需要注意的是，为了优化时间复杂度，可以提前计算出数组中所有数字的和 sum，以及数组的⻓度len。
//这样可以快速判断当前的和减去剩余的所有数是否已经超过了⽬标值 target ，
//或者当前的和加上剩下的数的和是否⼩于⽬标值 target，如果满⾜条件，则可以直接回溯。
//递归流程：
//1. 递归结束条件：index 与数组⻓度相等，判断当前状态的 sum 是否与⽬标值相等，若是计数加⼀；
//2. 选择当前元素进⾏加操作，递归下⼀个位置，并更新参数 sum；
//3. 选择当前元素进⾏减操作，递归下⼀个位置，并更新参数 sum；
//
//• 特别地，此问题可以转化为另⼀个问题：若所有元素初始状态均为减，
//选择其中⼏个元素将他们的状态修改为加，计算修改后的元素和与⽬标值相等的⽅案个数。
//
//1. 选择其中 x 个元素进⾏修改，并且这 x 个元素的和为 y；
//2. 检查使得 - sum + 2 * y = target（移项：y = (sum + target) / 2）成⽴的⽅案个数，即选择 x 个元素和为(sum + target) / 2 的⽅案个数；
//a.若 sum + target 为奇数，则不存在这种⽅案；
//3. 递归流程：
//a.传⼊参数：index（当前要处理的元素下标），sum（当前状态和），nums（元素数组），aim（⽬标值：(sum + target) / 2）；
//b.递归结束条件：index 与数组⻓度相等，判断当前 sum 是否与⽬标值相等，若是返回 1，否则返回 0；
//c.返回 递归选择当前元素 以及 递归不选择当前元素 函数值的和。

class Solution
{
    int count = 0, target;
public:
    int findTargetSumWays(vector<int>& nums, int t)
    {
        target = t;
        dfs(nums, 0, 0);
        return count;
    }
    void dfs(vector<int>& nums, int pos, int path)
    {
        if (pos == nums.size())
        {
            if (path == target)count++;
            return;
        }

        //+
        dfs(nums, pos + 1, path + nums[pos]);

        //-
        dfs(nums, pos + 1, path - nums[pos]);
    }
};